/**
题目:
    给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1：
输入：[1,2,3]

       1
      / \
     2   3
输出：6
示例 2：
输入：[-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7
输出：42
思路: 后序遍历
*/
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxPathSum(root *TreeNode) int {
    res := ^int(^uint32(0) >> 1)
    helper(&res, root)
    return res
}
func helper(res *int, root *TreeNode)int{
    if root == nil{
        return 0
    }
    left :=  max(helper(res,root.Left),0)
    right := max(helper(res,root.Right),0)
    *res = max(*res, root.Val + left + right)
    return  max(left,right) + root.Val
}
func max(a, b int)int{
    if a > b{
        return a
    }
    return b
}